#ifndef __PARKDRAGOMAN_H__
#define __PARKDRAGOMAN_H__

#include <iostream>
#include "adj_list_undir_network.h"
#include "char_string.h"
#include <fstream>
#include <cstring>

using namespace std;
class ParkDragoman
{
private:
    // 公园导游类的数据成员
    AdjListUndirNetwork<CharString, double> *pNet; // 由公园信息所建立的网
    ifstream *pInfile;                             // 输入流
    int maxNumOfShowPath;                          // 最多显示路线条数
    double **dist;                                 // 各对顶点u和v之间的最短路径长度 dist[u][v]
    int **path;                                    // 各对顶点u和v之间的最短路径 path[u][v]
    // 辅助函数
    int LocateVex(const CharString &e);      // 返回顶点元素元素在网中的位置
    void SkipOneLine();                      // 跳过一行
    void ShowTourismPath(int tourismPath[]); // 输出游览线路
    void CreatTourismPath(int to, int v, int tourismPath[], int pathVertexNum);
    // tourismPath 为游览路径，出口为to，v为当前顶点，pathVertexNum为路径当前顶点数
    void ShortestPathFloyd();   // 用Floyd算法求有向网net中各对顶点的最短路径
    void getPath(int u, int v); // 给出从u到v的最短路路径及路径长度
public:
    // 抽象数据类型方法的声明及重载系统默认方法的声明
    ParkDragoman(ifstream *pIFile); // 构造函数
    virtual ~ParkDragoman();        // 析构函数
    void run();                     // 公园导游
};

// 相关操作
static char GetChar(istream &instream);                            // 从输入流instream中跳过空格及制表符获取一字符
ostream &operator<<(ostream &outstream, const CharString &outStr); // 重载运算符<<
istream &operator>>(istream &instream, CharString &inStr);         // 重载运算符>>

char GetChar(istream &instream)
{
    char tmp;
    if (instream.peek() == EOF)
        return EOF;
    else
        tmp = instream.get();
    while (tmp == '\t' || tmp == ' ')
    { // 跳过制表符和空格
        tmp = instream.get();
    }
    return tmp;
}

ostream &operator<<(ostream &outstream, const CharString &outStr)
{
    cout << outStr.ToCStr();
    return outstream;
}

istream &operator>>(istream &inStream, CharString &inStr)
// 重载运算符>>
{
    LinkList<char> temp;
    int size = 0;
    char ch = GetChar(inStream);
    inStream.putback(ch);
    while ((ch = inStream.peek()) != EOF &&
           (ch = inStream.get()) != '\n' && ch != '\t' && ch != ' ')
    {
        temp.Insert(++size, ch);
    }
    CharString answer(temp);
    inStr = answer;
    return inStream;
}

void ParkDragoman::SkipOneLine()
{ // 跳过一行
    char tmp = GetChar(*pInfile);
    while (tmp != '\n' || tmp == EOF)
    {
        tmp = GetChar(*pInfile);
    }
}

void ParkDragoman::CreatTourismPath(int to, int v, int tourismPath[], int pathVertexNum)
// 初始条件：tourismPath 为游览路径，出口为to，v为当前顶点，pathVertexNum为路径当前顶点数
// 操作结果：生成并输出游览路径
{
    static int n = 0; // 已输出的游览线路个数

    for (int w = pNet->FirstAdjVex(v); w >= 0; w = pNet->NextAdjVex(v, w))
    { // 对v的所有邻接点进行循环
        // cout<<v<<" "<<w<<" "<<pNet->GetWeight(v,w)<<'\n';
        if (n == maxNumOfShowPath)
        {          // 已输出最多显示路线数
            break; // 退出循环
        }
        else if (!pNet->GetTag(w) && pathVertexNum == pNet->GetVexNum() - 1 && w == to && n < maxNumOfShowPath)
        {                                     // 得到一条游览路线
            ++n;                              // 已知游览线路个数自加1
            tourismPath[pathVertexNum++] = w; // 将w加入游览线路中
            ShowTourismPath(tourismPath);     // 输出游览线路
        }
        else if (!pNet->GetTag(w))
        {                                     // w未被访问过
            tourismPath[pathVertexNum++] = w; // 将w加入游览线路中
            pNet->SetTag(w, true);            // 重置访问标志为true
            CreatTourismPath(to, w, tourismPath, pathVertexNum);
            // 将w作为新的当前节点建立游览线路
            pathVertexNum--;        // 恢复路径顶点个数，回溯
            pNet->SetTag(w, false); // 重置访问标志为false，以便回溯
        }
    }
}

ParkDragoman::ParkDragoman(ifstream *pIFile)
// 操作结果：由输入文件建立表示公园信息的网
{
    pInfile = pIFile; // 输入文件
    char ch;          // 临时变量

    // 从输入流中输入景点数，景点数在"n="后面
    (*pInfile).seekg(0);    // 定位到文件开始处
    ch = GetChar(*pInfile); // 读字符
    while (ch != 'n')
    { // 查找以'n'开始的行
        if (ch != '\n')
            SkipOneLine();      // 跳行
        ch = GetChar(*pInfile); // 读入字符
    }
    GetChar(*pInfile);                      // 跳过"="
    int n;                                  // 景点数
    *pInfile >> n;                          // 读入景点数
    CharString *es = new CharString[n + 2]; // 网顶点元素，包括景点与出入口
    // 从输入流中输入景点名称，景点数在"v="后面，假设景点名不含空格，不同景点之间用空格分隔
    (*pInfile).seekg(0);    // 定位到文件开始处
    ch = GetChar(*pInfile); // 读字符
    while (ch != 'v')
    { // 查找以'v'开始的行
        if (ch != '\n')
            SkipOneLine();      // 跳行
        ch = GetChar(*pInfile); // 读入字符
    }
    GetChar(*pInfile); // 跳过"="
    int i;             // 临时变量
    for (i = 0; i < n; i++)
    {                      // 读入景点名称
        *pInfile >> es[i]; // 从输入流*pInFile中输入景点名称
    }
    es[n] = "入口";     // 入口
    es[n + 1] = "出口"; // 出口

    // 从输入流中输入最多显示路线条数，最多显示路线条数在"s="后面
    (*pInfile).seekg(0);    // 定位到文件开始处
    ch = GetChar(*pInfile); // 读字符
    while (ch != 's')
    { // 查找以's'开始的行
        if (ch != '\n')
            SkipOneLine();      // 跳行
        ch = GetChar(*pInfile); // 读入字符
    }
    GetChar(*pInfile);            // 跳过"="
    *pInfile >> maxNumOfShowPath; // 读入最多显示路线条数

    pNet = new AdjListUndirNetwork<CharString, double>(es, n + 2);
    // 生成网

    // 从输入流中输入边信息
    (*pInfile).seekg(0);    // 定位到文件开始处
    ch = GetChar(*pInfile); // 读字符
    while (true)
    { // 文件未结束
        while (ch != '(' && ch != EOF)
        { // 查找以"("开始的行或输入流已结束
            if (ch != '\n')
                SkipOneLine();      // 跳行
            ch = GetChar(*pInfile); // 读入字符
        }
        if (ch == EOF)
            break;                   // 输入流已结束
        CharString e1, e2;           // 边顶点元素
        int v1, v2;                  // 边顶点
        double w;                    // 权值
        (*pInfile) >> e1 >> e2 >> w; // 读入顶点元素及权值
        if ((v1 = LocateVex(e1)) == -1)
        {
            cout << "边顶点元素错！" << endl;
            exit(1);
        }
        // 出现异常
        if ((v2 = LocateVex(e2)) == -1)
        {
            cout << "边顶点元素错！" << endl;
            exit(2);
        }
        // 出现异常
        pNet->InsertEdge(v1, v2, w); // 插入边
        ch = GetChar(*pInfile);      // 读入字符
    }

    dist = new double *[pNet->GetVexNum()], path = new int *[pNet->GetVexNum()];
    // 分配空间
    for (i = 0; i < pNet->GetVexNum(); i++)
    { // 对二维数组的每一行分配空间
        dist[i] = new double[pNet->GetVexNum()];
        path[i] = new int[pNet->GetVexNum()];
    }
    ShortestPathFloyd(); // 用Floyd算法求无向网net中各对顶点u和v之间的最短路径
}

ParkDragoman::~ParkDragoman()
{
    for (int i = 0; i < pNet->GetVexNum(); i++)
    { // 析构函数
        delete dist[i];
        delete path[i];
    }
    delete pNet;
    delete[] dist;
    delete[] path;
}

void ParkDragoman::ShortestPathFloyd()
{
    double INF = 10000;
    for (int u = 0; u < pNet->GetVexNum(); u++)
    {
        for (int v = 0; v < pNet->GetVexNum(); v++)
        {
            dist[u][v] = (u == v || pNet->GetWeight(u, v) == 0) ? INF : pNet->GetWeight(u, v);
            if (u != v && dist[u][v] < INF)
                path[u][v] = u;
            else
                path[u][v] = -1;
        }
    }

    for (int k = 0; k < pNet->GetVexNum(); k++)
        for (int i = 0; i < pNet->GetVexNum(); i++)
            for (int j = 0; j < pNet->GetVexNum(); j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = path[k][j];
                }
}

void ParkDragoman::ShowTourismPath(int tourismPath[])
// 操作结果：输出一条路径
{
    CharString tmp;    // 中间变量
    double length = 0; // 中间变量
    cout << "线路：入口";
    for (int i = 1; i < 12; i++) // 遍历路径
    {
        pNet->GetElem(tourismPath[i], tmp);
        cout << tmp << " ";
        length += dist[tourismPath[i - 1]][tourismPath[i]];
    }
    cout << "\n长度：" << length << "\n\n"; // 换行
}

void ParkDragoman::getPath(int u, int v)
// 操作结果：输出从u到v的最短路径及路径长度
{
    cout << "最短路径长度为：" << dist[u][v] << "\n最短路径：";
    int a = u, b = v;
    CharString tmp;
    pNet->GetElem(a, tmp);
    cout << tmp << " ";
    while (a != v && path[a][v] != a)
    {
        if (path[a][b] != 0)
        {
            b = path[a][b];
        }
        else
        {
            a = b;
            b = v;
            pNet->GetElem(a, tmp);
            cout << tmp << " ";
        }
    }
    pNet->GetElem(v, tmp);
    cout << tmp << "\n\n";
}

int ParkDragoman::LocateVex(const CharString &e)
// 操作结果：返回景点在网中的位置，若不存在，则返回-1
{
    int i;
    CharString tmp;
    const char *tmp1 = e.ToCStr(); // 临时变量
    const char *tmp2;              // 临时变量
    for (i = 0; i < pNet->GetVexNum(); i++)
    {
        pNet->GetElem(i, tmp);
        tmp2 = tmp.ToCStr();
        if (strcmp(tmp1, tmp2) == 0) // 遍历进行比较
        {
            return i;
        }
    }
    return -1; // 景点不存在，返回-1
}

void ParkDragoman::run()
// 操作结果：开始公园导航
{
    int in;              // 临时变量
    CharString from, to; // 临时变量
    while (true)
    {
        cout << "1.最短路径\n2.游览线路\n3.退出\n";
        cin >> in;
        getchar(); // 跳过换行符
        switch (in)
        {
        case 1:
            // 查询两个景点间的最短路径和长度
            cout << "起点：";
            from = Read(cin);
            cout << "终点：";
            to = Read(cin);
            getPath(LocateVex(from), LocateVex(to));
            break;
        case 2:
            // 输出一条游览线路
            int tmp[12];
            tmp[0] = LocateVex("入口");
            cout << "游览线路及长度：\n";
            CreatTourismPath(LocateVex("出口"), LocateVex("入口"), tmp, 1);
            ;
            break;
        case 3:
            // 退出程序
            return;
        default:
            break;
        }
    }
}

#endif